1. Field of the Invention
This invention relates to virtual memory systems and, more particularly, to memory management units for controlling the translation of addresses between virtual and physical memory.
2. History of the Prior Art
Two general trends have coincided in the development of computer systems. The first is that the addressable memory available to a computer has grown larger so that the computer may handle more information and larger, more sophisticated programs. The second is that the speed of operation of a computer has increased so that larger programs may be run in a reasonable time.
One of the ways in which the addressable memory of a computer has been increased is through the use of virtual memory systems. A virtual memory system allows addressing of very large amounts of memory as though all of that memory were a part of the main memory of the computer system. A virtual memory system allows this even though actual main memory may consist of some substantially lesser amount of storage space than is addressable. For example, main memory may consist of one megabyte of random access memory while sixty-four megabytes of memory are addressable using the virtual memory addressing system.
Virtual memory systems accomplish this feat by providing memory management units which translate virtual memory addresses into the physical memory addresses at which the information actually resides. A particular physical address holding the information may be in main memory or in long term storage such as a hard disk. If the physical address of information sought is in main memory, the information is accessed and utilized by the computer. If the physical address is in long term storage, the information is transferred (usually in a block referred to as a page) to main memory where it may be used. This transfer may necessitate that other information be swapped out of main memory to long term memory in order to make room for the new information. If so, this is accomplished under control of the memory management unit.
The pages referred above are, if fact, the usual means for addressing information. Pages are numbered, and both physical and virtual addresses typically includes a page number and an offset into the page. Moreover, the physical offset and the virtual offset are typically the same. In order to translate between virtual and physical addresses, a basic virtual memory system creates lookup tables which are stored in main memory. These lookup tables store the virtual address page numbers used by the computer. Stored with each virtual address page number is the physical address page number which must be accessed to derive the information. The page number of any virtual address presented to the memory management unit is compared to the values stored in these tables in order to find a matching virtual address page number and retrieve the physical address page number.
There are often several levels of tables, and the comparison takes a great deal of system clock time. For example, to retrieve a physical page address using the lookup tables stored in main memory, the typical memory management unit first looks to a register for the address of a base table which stores pointers to other levels of tables. The memory management unit retrieves this pointer from the base table and places it in another register. The memory management unit uses this pointer to go to the next level of table. This process continues until the physical page address of the information sought is recovered. When the physical address is recovered, it is combined with the offset furnished as a part of the virtual address; and the result is used by the processor to access the particular information desired. A typical lookup in the page tables may take from ten to fifteen clock cycles at each level of the search.
To overcome this delay, virtual memory management systems often include cache memories called translation lookaside buffers (TLBs). A translation lookaside buffer is essentially a buffer for caching virtual page addresses which have been recently used along with their related physical page addresses. Such an address cache works on the same principle as do caches holding data and instructions, the most recently used addresses are more likely to be used than are other addresses. When provided a virtual page address which is stored in the translation lookaside buffer, the translation lookaside buffer furnishes a physical page address for the information without the necessity of consulting the page lookup tables. It is only when the processor sends a virtual page address to the translation lookaside buffer which address is not stored in the translation lookaside buffer that the memory management unit must consult the page lookup tables. When this occurs, the physical page address recovered is stored along with the virtual page address in the translation lookaside buffer so that the next time it is needed it is immediately available. This saves a great deal of time on the next use of the information. For example, accessing the information using a translation lookaside buffer may require only one or two clock cycles compared to hundreds of clock cycles required for a page table lookup.
Presently, computers are designed to use only a single page size; and a designer must choose that size based on certain assumptions about the use of the computer. For example, the storage of a single frame of twenty-four bit color information for the output display requires megabytes of memory space. However, the typical page size utilized in a virtual memory system is four kilobytes. Since each page requires at least one page table translation, the access of a display frame of data requires at least one thousand individual references to the memory management unit to accomplish the translation of the addresses necessary to access the frame buffer in memory. Thus, it would be much more convenient and faster for a computer possessor in dealing with display memory if the data were all to be included in a single page of memory so that the page address translation necessary to display a single frame on the output display could be accomplished for a single page rather than one thousand different pages. On the other hand, if only such large page sizes were to be available, then a very large number of addresses would be wasted since most processes require less than the typical four kilobyte byte page size now utilized.
One way in which the speed of operation of a computer which uses a virtual memory system might be increased would be to allow the virtual memory to utilize many different sizes of pages.
Although it would be desirable to provide multiple page sizes for virtual memory, in order to do so, a system would need to find ways to store different page sizes together in a translation lookaside buffer, to test different page sizes for a hit in the translation lookaside buffer, and to use different size pages to look up addresses. All of these and more are very difficult problems that had not been resolved prior to the present invention.